home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / docs / winer / seeqsort.bas < prev    next >
Encoding:
BASIC Source File  |  1992-05-13  |  3.6 KB  |  176 lines
  1. '********* SEEQSORT.BAS - Quick Sort algorithm visual demonstration
  2.  
  3. 'Copyright (c) 1992 Ethan Winer
  4.  
  5. DEFINT A-Z
  6. DECLARE SUB SeeQSort (Array!())
  7.  
  8. RANDOMIZE TIMER         'generate a new series each run
  9.  
  10. CONST MaxElements = 23  'the size of the text array
  11. CONST Delay! = 1!       'pause delay, change to suit
  12. CONST FG = 7            'the foreground color
  13. CONST BG = 1            'the background color
  14. CONST Hi = 15 + 16      'high-intensity flashing
  15.  
  16. DIM Array!(1 TO MaxElements)    'create an array
  17. FOR X = 1 TO MaxElements        'fill with random numbers
  18.   Array!(X) = RND(1) * 500      'between 0 and 500
  19. NEXT
  20.  
  21. COLOR FG, BG
  22. CLS
  23. LOCATE 25, 1
  24. PRINT "Press Escape to end the program early"; TAB(80);
  25. CALL SeeQSort(Array!())
  26.  
  27. SUB SeeQSort (Array!()) STATIC
  28.  
  29. REDIM QStack(10)        'create a stack big enough for this example
  30.  
  31. First = LBOUND(Array!)  'initialize work variables
  32. Last = UBOUND(Array!)
  33.  
  34. DO
  35.   DO
  36.     Temp! = Array!((Last + First) \ 2)  'seek midpoint
  37.     I = First
  38.     J = Last
  39.  
  40.     DO     'reverse both < and > below to sort descending
  41.       WHILE Array!(I) < Temp!
  42.         I = I + 1
  43.         GOSUB UpdateScreen
  44.         GOSUB Pause
  45.       WEND
  46.       WHILE Array!(J) > Temp!
  47.         J = J - 1
  48.         GOSUB UpdateScreen
  49.         GOSUB Pause
  50.       WEND
  51.       IF I > J THEN EXIT DO
  52.       IF I < J THEN
  53.         LOCATE 1, 60
  54.         COLOR BG, FG
  55.         PRINT " About to swap ";
  56.         COLOR Hi, BG
  57.         LOCATE I, 39
  58.         PRINT USING "####.## "; Array!(I);
  59.         LOCATE J, 39
  60.         PRINT USING "####.## "; Array!(J);
  61.         COLOR FG, BG
  62.         GOSUB Pause
  63.         SWAP Array!(I), Array!(J)
  64.         GOSUB UpdateScreen
  65.         LOCATE 1, 60
  66.         COLOR BG, FG
  67.         PRINT "    Swapped    ";
  68.         GOSUB Pause
  69.       END IF
  70.  
  71.       I = I + 1
  72.       J = J - 1
  73.     LOOP WHILE I <= J
  74.  
  75.     IF I < Last THEN                    'Done
  76.       LOCATE 1, 60
  77.       COLOR BG, FG
  78.       PRINT " About to push ";
  79.       GOSUB Pause
  80.       QStack(StackPtr) = I              'Push I
  81.       QStack(StackPtr + 1) = Last       'Push Last
  82.       StackPtr = StackPtr + 2
  83.       GOSUB UpdateScreen
  84.       LOCATE 1, 60
  85.       COLOR BG, FG
  86.       PRINT "     Pushed    ";
  87.       GOSUB Pause
  88.     END IF
  89.  
  90.     Last = J
  91.   LOOP WHILE First < Last
  92.  
  93.   IF StackPtr = 0 THEN EXIT DO
  94.  
  95.   LOCATE 1, 60
  96.   COLOR BG, FG
  97.   PRINT " About to pop ";
  98.   GOSUB Pause
  99.   StackPtr = StackPtr - 2
  100.   First = QStack(StackPtr)              'Pop First
  101.   Last = QStack(StackPtr + 1)           'Pop Last
  102.   GOSUB UpdateScreen
  103.   LOCATE 1, 60
  104.   COLOR BG, FG
  105.   PRINT "    Popped    ";
  106.   GOSUB Pause
  107. LOOP
  108.  
  109. ERASE QStack               'delete the stack array
  110. COLOR FG, BG
  111. EXIT SUB
  112.  
  113. UpdateScreen:
  114.   COLOR FG, BG
  115.   LOCATE 1, 60
  116.   PRINT SPC(15);
  117.  
  118.   FOR X = 1 TO MaxElements
  119.     LOCATE X, 24
  120.     IF X = (Last + First) \ 2 THEN
  121.       COLOR BG, FG
  122.       PRINT " Midpoint ==> "
  123.       COLOR FG, BG
  124.     ELSE
  125.       PRINT SPC(14);
  126.     END IF
  127.   
  128.     LOCATE X, 1
  129.     IF X = First THEN
  130.       COLOR BG, FG
  131.       PRINT " First ==> "
  132.       COLOR FG, BG
  133.     ELSE
  134.       PRINT SPC(11);
  135.     END IF
  136.    
  137.     LOCATE X, 13
  138.     IF X = Last THEN
  139.       COLOR BG, FG
  140.       PRINT " Last ==> "
  141.       COLOR FG, BG
  142.     ELSE
  143.       PRINT SPC(11);
  144.     END IF
  145.  
  146.  
  147.     LOCATE X, 39
  148.     PRINT USING "####.## "; Array!(X);
  149.     PRINT SPC(17);
  150.     COLOR BG, FG
  151.     LOCATE X, 48
  152.  
  153.     IF X = I THEN
  154.       PRINT " <== I "
  155.     END IF
  156.     IF X = J THEN
  157.       LOCATE X, 56
  158.       PRINT " <== J "
  159.     END IF
  160.  
  161.     COLOR FG, BG
  162.   NEXT
  163. RETURN
  164.  
  165.  
  166. Pause:
  167.   Start! = TIMER
  168.   DO
  169.   LOOP WHILE Start! + Delay! > TIMER
  170.  
  171.   IF INKEY$ = CHR$(27) THEN END
  172.  
  173.   RETURN
  174.  
  175. END SUB
  176.